package q128_longestConsecutive;

import java.util.HashSet;
import java.util.Set;

public class Solution_1 {

    /**
     * 最长连续序列：最核心的要求在于设置了时间复杂度不超过O(n)
     * 我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配 x+1, x+2, ... 是否存在，假设最长匹配到了 x+y，
     * 那么以 x 为起点的最长连续序列即为x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可
     * 但是这样的情况下复杂度可能达到O(n^2)
     * 其中执行了很多不必要的枚举，如果已知有一个x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，
     * 那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
     * 那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x-1 的，不然按照上面的分析我们会从 x-1 开始尝试匹配，
     * 因此我们每次在哈希表中检查是否存在 x-1 即能判断是否需要跳过了
     *
     * 该题具有四种思路，可见题解
     * https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/xiao-bai-lang-ha-xi-ji-he-ha-xi-biao-don-j5a2/
     */
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        // 首先将所有的数字先加入hashSet
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;
        // 开始遍历
        for (int num : num_set) {
            // 这里先判断当前的数字是不是已经有前驱的数字了，如果有的话，那么我们应该从前驱的数字开始匹配
            if (!num_set.contains(num - 1)) {
                // 进入循环就意味着没有前驱数字
                int currentNum = num;
                int currentStreak = 1;
                // 我们只需要反复循环找到当前这个没有前驱数字最远到达的位置即可
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                // 然后再找出最长的部分
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;

    }
}
